#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/7/10 17:34
# ===========================================
#       题目名称： 66. 加一
#       题目地址： https://leetcode.cn/problems/plus-one/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:
    def plusOne(self, digits):
        digits.reverse()
        digits[0] += 1
        cur_index = 0
        while True:
            if digits[cur_index] / 10 == 1:
                if cur_index > len(digits) - 1:
                    digits.append(1)
                    digits[cur_index] %= 10
                    break
                else:
                    digits[cur_index] %= 10
                    if cur_index + 1 > len(digits) - 1:
                        digits.append(1)
                    else:
                        digits[cur_index + 1] += 1
                        cur_index += 1
            else:
                break
        digits.reverse()
        return digits


    def plusOne2(self, digits):
        """
            算法有问题
        """
        # 从打到小遍历
        cur_index = len(digits) - 1  # 当前下标
        is_carry = False
        while is_carry or cur_index > -1:
            val = digits[cur_index] + 1
            if cur_index == len(digits) - 1:
                if val >= 10:
                    is_carry = True
                    val -= 10
                digits[cur_index] = val
                cur_index -= 1
            elif is_carry:
                if val >= 10:
                    val -= 10
                else:
                    is_carry = False
                if cur_index < 0:
                    digits.insert(0, val)
                cur_index -= 1
            else:
                break
        return digits


if __name__ == '__main__':
    s = Solution()
    # [1,2,4]
    print("digits = [1,2,3] => ", s.plusOne(digits=[1, 2, 3]))
    # [4,3,2,2]
    print("digits = [4,3,2,1] => ", s.plusOne(digits=[4, 3, 2, 1]))
    # [1,0]
    print("digits = [9] => ", s.plusOne(digits=[9]))
    # [1,0,0]
    print("digits = [9, 9] => ", s.plusOne(digits=[9, 9]))
